#include <iostream>
#include <assert.h>
#include <vector>
using namespace std;
//#include "../c-plus-plus/2025_01_23_RBTree/RBTree.h"
#include "RBTree.h"
#include "AVLTree.h"
const size_t N = 10000000;
void RBTreeTest1()
{
    Aurora::RBTree<int,int> rb;
    //常规测试用例
    int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
    //特殊带有双旋场景测试用例
    //int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
    for(const auto& e : a)
    {
        rb.Insert({e,e});
    }
    rb.InOrder();
    cout << rb.Size() << endl;
    cout << rb.Hight() << endl;
    //cout << rb.IsRBTree() << endl;
}
void RBTreeTest2()
{
    Aurora::RBTree<int,int> rb;
    vector<int> v;
    srand(time(0));
    for(size_t i = 0;i < N;i++)
    {
        v.push_back(rand() + i);
    }
    size_t begin1 = clock();
    for(const auto& e : v)
    {
        rb.Insert({e,e});
    }
    rb.Insert({4399,4399});
    size_t end1 = clock();
    size_t begin2 = clock();
    int x = rand();
    Aurora::RBTreeNode<int,int>* f = rb.Find(x);
    //Aurora::RBTNode<int,int>* f = rb.Find(x);
    if(f != nullptr) cout << "找到了" << f->_kv.first << ":" << f->_kv.second << endl;
    else cout << "没找到" << endl;
    size_t end2 = clock();
    //rb.InOrder();
    cout << "Insert:" << end1 - begin1 << "ms" << endl;
    cout << "Find:" << end2 - begin2 << "ms" << endl;
    cout << "Size:" << rb.Size() << "个" << endl;
    cout << "Hight:" << rb.Hight() << "层" << endl;
    cout << "IsRBTree:" << rb.IsRBTree() << endl;
    //cout << "IsRBTree:" << rb.IsBalance() << endl;
}
void AVLTreeTest1()
{
    Aurora::AVLTree<int,int> av;
    //常规测试用例
    //int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
    //特殊带有双旋场景测试用例
    int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
    for(const auto& e : a)
    {
        av.Insert({e,e});
    }
    //av.InOrder();
    cout << av.IsAVLTree() << endl;
}
void AVLTreeTest2()
{
    Aurora::AVLTree<int,int> av;
    vector<int> v;
    srand(time(0));
    for(size_t i = 0;i < N;i++)
    {
        v.push_back(rand()+i);
    }
    size_t begin1 = clock();
    for(const auto& e : v)
    {
        av.Insert({e,e});
    }
    size_t end1 = clock();
    size_t begin2 = clock();
    int x = rand();
    Aurora::AVLTreeNode<int,int>* f = av.Find(x);
    if(f != nullptr) cout << "找到了" << f->_kv.first << ":" << f->_kv.second << endl;
    else cout << "没找到" << endl;
    size_t end2 = clock();
    cout << "Insert:" << end1 - begin1 << "ms" << endl;
    cout << "Find:" << end2 - begin2 << "ms" << endl;
    cout << "Size:" << av.Size() << "个" << endl;
    cout << "Hight:" << av.Hight() << "层" << endl;
    cout << "IsAVLTree:" << av.IsAVLTree() << endl;
}
int main()
{
    cout << "插入" << N << "个随机值,红黑树和AVL树性能对比" << endl;
    cout << "********红黑树性能测试结果********" << endl;
    RBTreeTest2();
    cout << "********AVL树性能测试结果********" << endl;
    AVLTreeTest2();
    return 0;
}